1. Field of the Invention
The present invention relates to cryptographic techniques, and more particularly to methods and apparatus for implementing certificate schemes based on public-key cryptography.
2. Description of the Prior Art
Public-key certificates, usually plainly referred to as certificates, are an essential cryptographic tool for secure key management. The idea is to have a specially appointed party, commonly called the Certification Authority, certify the public keys of other parties in the system by digitally signing these public keys with its own secret key. By widely distributing the public key of the Certification Authority through a variety of media, one can be assured that it is genuine. Because a public-key certificate is a digital signature of the Certification Authority on a public key, certificates on public keys of other parties can be verified by anyone by using the public key of the Certification Authority. The net effect is that impersonation attacks, and similar other attacks, are prevented.
In practical applications, the certificate of the Certification Authority may, and perhaps should, certify additional information. Along with the public key, a certificate could validate such information as the name of the party associated with the public key, employer, telephone number, electronic mail address, and a list of access rights.
To facilitate practicality of the certificate issuing process, public keys can be recursively certified according to a hierarchical structure. For example, in an electronic cash system, the main bank can certify the public keys of all the local banks, the local banks in turn can certify public keys in POS terminals by using their certified keys, and the secret keys corresponding to the public keys in the POS terminals can be used to decrypt information that is sent by the host. The hierarchic certification process can be thought of as building a tree, each node containing a public key and a certificate on the public key. A certificate on a public key in a node is a digital signature on that public key, that has been computed by the party associated with the parent node by applying the secret key that corresponds to the public key of the parent node. Anyone can verify the validity of a public key be recursively descending (or ascending) the tree from the root node to the node associated with the public key that is being verified (or vice versa). A certification hierarchy that is often suggested is one that is implied by the life-time of the cryptographic keys: keys that are more susceptible to attacks are changed more frequently, and are certified by keys that have a longer life-time.
Public keys can be listed in so-called public-key directories, which can be made available on CD-ROM or other media. In order to encrypt a message intended for another party, one needs to merely look up the public key of that other party in the public-key directory, verify the validity of the certificate, and encrypt the message with the public key. It can then be sent to the other party. No interaction is needed between the two parties. In this way for instance encrypted electronic mail can be sent over a computer network.
Because the certificate mechanism obviates the need for the public-key directory to be secured, public keys need not necessarily be listed in a public-key directory. They may be sent (along with the certificate) on request, by the party associated with the public key itself, or by any other party that need not be trusted, such as a server in a computer network.
In cryptographic mechanisms for transfer of credentials, the Certification Authority at issuing time can issue a certificate on a public key of a user; the type of credential that is issued can, for instance, be denoted by the type of signature that the Certification Authority computes. This allows the user, when transferring the credential to a recipient, to make a digital signature on a message of the recipient (describing such information as the identity of the recipient and transaction details), by using the secret key corresponding to his certified public key. The certificate proves the validity of the credential to the recipient, whereas the signature made by the user proves that the user willingly transferred the credential to the recipient.
For privacy-protected transfer of credentials, the information that is issued by the Certification Authority should not be linkable to executions of the issuing protocol. Special techniques are known that enable the user to blind the issuing protocol while interacting with the Certificate Authority.
While important and useful, the public-key certificate technique also has a few problems associated with it. First of these relates to privacy. It is conceivable that providers for a variety of electronic systems available in the new future will require participants to meet certain criteria before certifying their public keys. These criteria may include social status, income, type of job, trustworthiness, and so on. Because a public-key certificate is a digital signature of the Certification Authority on the public key, pairs consisting of a public key and a corresponding public-key certificate reveal to anyone which parties are participating in a certain system, and which parties are not participating. This reveals which parties meet the criteria specified by the Certification Authority, and which parties may not meet them. Likewise, the genuineness of the additional information (employer, telephone number, access rights, and so on) that may have been certified along with the public key, is revealed. Consequently, public-key certificates allow anyone to extract profiles of other parties, by scanning for their appearances, or the lack thereof, in compiled lists of certified public keys (such as public-key directories). This problem is by no means removed by letting participants send their public keys only on request, instead of using a public-key directory.
A second problem is that the publication of a public-key directory reveals a huge amount of digital signatures of the Certification Authority on known, or chosen, public keys. Although most of the known digital signature schemes are believed to be secure under known, or (adaptively) chosen, message attacks, only a few signature schemes are known that can be proven to be secure, assuming the existence of functions that are substantially unfeasible to invert. Unfortunately, these schemes are currently not practical for large-scale use. Since public-key directories typically will contain an enormous amount of entries, the Certification Authority will have to use an efficient signature scheme. This implies that the signatures in the public-key directory may be helpful in attempts to break the signature scheme of the Certification Authority; they can be used to mount known or (adaptively) chosen message attacks. Again, this problem is not removed by letting participants send their public keys only on request, instead of using a public-key directory.
A third problem is in blinding public-key certificate issuing protocols in mechanism for privacy-protected transfer of credentials (see, for instance, U.S. Pat. No. 4,759,063 to Chaum for a discussion of the technique of blinding in public-key cryptography). In many circumstances, the Certification Authority does not want the users to be able to blind to their hearts' contents, but would like to encode information in the issued information that cannot be changed by the blinding operations of the user. For instance, the mechanisms for transferring credentials under pseudonym, this encoded information can be uniquely associated with the user that the credential is issued to, thereby linking the pre-images of all the pseudonyms of each user. In this way, it can be ensured that users cannot use the credentials of other users, even if they cooperate. For credentials that may be shown only a limited number of times, such as coins in an electronic can system, it can be arranged that this encoded information is revealed if and only if the credential is shown a number of times exceeding a predetermined limit. This obviates the need for on-line verification of these credentials. For such purposes, an issuing protocol is needed in which the Certification Authority issues a secret key, a public key, and a public-key certificate, in such a way that the public key and the certificate can be perfectly blinded by the user, by a non-constant function of the secret key cannot. Such an issuing protocol is called a restrictive blind signature issuing protocol, and is described and claimed in patent application Ser. No. 08/203,231, filed Feb. 28, 1994, and is incorporated by reference herein. From the point of view of security, no satisfactory constructions of restrictive blind signature issuing protocols are known in which the certificate is a public-key certificate. This is a serious problem, since restrictive blind signature issuing protocols are of crucial importance for the construction of efficient and secure mechanisms for privacy-protected off-line transfer of credentials.
Patent application Ser. No. 08/203,231, filed Feb. 28, 1994, also describes and claims an inventive method for constructing restrictive blind signature issuing protocols where the issued certificate is not a digital signature on the public key (and hence not a public-key certificate). As is demonstrated in detail, the construction of efficient and secure restrictive blind signature issuing protocols becomes much easier by removing the need for the certificate to be a signature of the issuer on the public key. Most (more specifically, all but the last one described) of the exemplary restrictive blind signature issuing protocols described and claimed in patent application Ser. No. 08/203,231 are constructed by applying this inventive method.
While the inventive method described and claimed in patent application Ser. No. 08/203,231 overcomes the third problem associated with public-key certificates, it does not address the first two problems. This invention describes a generalized method that also overcomes the first two problems associated with public-key certificates.